import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: LIUYANJIAO
 * Date: 2024-10-28
 * Time: 20:38
 */
public class Main {
    public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
         this.val = val;
         this.left = left;
         this.right = right;
      }
  }

    public String tree2str(TreeNode root) {
        if(root==null) return "";
        if(root.left==null&&root.right==null){
            return Integer.toString(root.val);
        }
        if(root.left!=null&&root.right==null){
            return new StringBuilder().append(root.val).append("(").append(tree2str(root.left)).append(")").toString();
        }
        return new StringBuilder().append(root.val).append("(").append(tree2str(root.left)).append(")")
                .append(tree2str(root.right)).append(")").toString();

    }
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        if(root==null) return null;
        //创建一个二维链表
        List<List<Integer>> list=new ArrayList<>();
        //普通的层序遍历
        //创建一个队列
        Deque<TreeNode> deque=new ArrayDeque<>();
        while(root!=null||!deque.isEmpty()){
            while(deque.isEmpty()){
                deque.offer(root);
            }

            int size=deque.size();
            //创建一个一维链表
            List<Integer> l=new ArrayList<>();
            for (int i = 0; i < size; i++) {
                //队列中插入子树
               if(root.left!=null) deque.offer(root.left);
               if(root.right!=null) deque.offer(root.right);
                //将目前队列中的数据存储到链表中
                l.add(deque.pop().val);
                root=deque.peek();
            }
            //因为顺序为自下而上，所以为头插
            list.add(0,l);

        }
        return list;
    }
    public static void main(String[] args) {


    }
}